/**
 * 
 */
package BNS.coloring;

import java.io.BufferedWriter;
import java.io.File;
import java.io.FileWriter;
import java.io.IOException;
import java.util.Random;
import java.util.Vector;

import BNS.graphs.MatrixGraph;

/**
 * @author iggardne
 *
 */
public class SimulationHamming {
	public static final int NUMBER_OF_STEPS = 100000;
	public static final int NUMBER_OF_SIMULATIONS = 10000;
	
	public static final boolean DEBUG = false;
	public static final boolean SOLUTIONS = false;
	public static final String SEP = ",";
	public static final String SEP2 = "\n";
	private static BufferedWriter DATA_OUT;
	private final SimuGraph gr;
	private final int numNodes;
	private int chroma;
	private long solutions;
	private final Vector<SimuNode> nodes;
	private final Vector<Vector<SimuNode>> neighbors;
	private final Vector<SimuEdge> edges;
	private int MOVES;
	private int NON_MOVES;
	private int HALF_MOVES;
	private int NUM_CHOICES;
	private int LAST_MOVE;
	private String CURRENT_FILE;
	
	public enum Algorithm {
		RAREST,RANDOM_RAREST
	}
	
	/**
	 * This sets up the graph and the data structures (neighbors vector)
	 * that are used for the chromatic number and simulation algorithms.
	 * 
	 * @param file - contains a graph in adjacency matrix form.
	 */
	public SimulationHamming(File file) {
		gr=new SimuGraph(MatrixGraph.create(file));
		nodes=gr.nodes;
		edges=gr.edges;
		numNodes=nodes.size();
		
		//create the vectors that will hold the neighbors of each node
		neighbors=new Vector<Vector<SimuNode>>();
		for(int i=0;i<nodes.size();i++)
			neighbors.add(new Vector<SimuNode>());
		
		//add node to to node from's neighbor vector
		//add node from to node to's neighbor vector
		for(SimuEdge e:edges) {
			neighbors.get(e.from.index).add(e.to);
			neighbors.get(e.to.index).add(e.from);
		}
		
		
		/*for(Node n:nodes) {
			System.err.print(n.getIndex()+": neighbors are:");
			for(Node ne:neighbors.get(n.getIndex()))
				System.err.print(" "+ne.getIndex());
			System.err.println();
		}*/
	}
	
	/**
	 * check if node has any neighbors that are color. If yes return false,
	 * if no return true;
	 * 
	 * @param node - the node to check the neighbors of
	 * @param color - the color to check the neighbors against
	 * @return
	 */
	public boolean available(int node,int color) {
		for(SimuNode curr:neighbors.get(node))
			if(curr.color==color) return false;
		return true;
	}
	
	/**
	 * This method finds the chromatic number of a graph.
	 * It starts at chroma and then recursively calls itself, with chroma
	 * plus one until it finds the chromatic number.
	 * 
	 * @param chroma - the first chromatic number to check
	 * @return the chromatic number of the current graph
	 */
	public int chromaticNumber(int chroma) {
		if(chroma==nodes.size()) return nodes.size();
		
		this.chroma=chroma;
		
		//Node node=nodes.get(0);node.
		//System.out.println("Colors:"+chroma);
		
		if(chromaColorable(0)) return chroma;
		
		return chromaticNumber(chroma+1);
	}
	
	/**
	 * Recursive function to find if a graph can be colored with chroma
	 * colors. It is a brute force algorithm that only checks possible
	 * combinations.
	 * 
	 * @param node - the next node to check
	 * @return - true if the graph is colorable false otherwise
	 */
	public boolean chromaColorable(int node) {
		
		if(node==nodes.size()) {
			//for(SimuNode n:nodes) {
			//	System.err.print(n.index + ":"+ n.color+", ");
			//}
			return true;
		}
		
		for(int i=1;i<=chroma;i++) {
			if(available(node,i)) {
				nodes.get(node).color=i;
				if(chromaColorable(node+1)) return true;
			}
		}
		//if(node<=2) System.out.println(chroma+": Exiting: "+node);

		nodes.get(node).color=0;
		return false;
	}
	
	/**
	 * Returns the number of solutions in the current graph with the the
	 * current chroma set. Simply a helper function, calls solutions(0) and
	 * then return the internal variable that is set.
	 *  
	 * @return - the number of solutions
	 */
	public long solutions() {
		solutions=0;
		solutions(0);
		//System.out.println("Chromaaaaaaaaa::::"+chroma);
		return solutions;
	}
	
	/**
	 * Follows a similar algorithm to chromaColorable, but does not stop when
	 * the first solution is found, it continues and finds every solution
	 * for the current graph with the current chroma set
	 *  
	 * @param node - the next node to check
	 */
	public void solutions(int node) {
		//System.err.println("entering "+node);
		//System.out.println(chroma);
		if(node==nodes.size()) {
			//if(gr.colored(true)) {
			solutions++;
			//for(Node n:nodes)
			//	System.err.print(n.getIndex()+1+":"+n.color+" ");
			//System.err.println();
			//}
			return;
		}
		else { 
		for(int i=1;i<=chroma;i++) {
			if(available(node,i)) {
				//System.err.println(node+":"+i);
				nodes.get(node).color=i;
				solutions(node+1);
			}
		}
		}
		nodes.get(node).color=0;
		//System.err.println("leaving "+node);
	}

	public void buildSolutionVector() {
		solutions = 0;
		solutionVector = new Vector<Vector<Integer>>();
		solutionBuild(0);
	}
	private Vector<Vector<Integer>> solutionVector;
	public void solutionBuild(int node) {
		if(node==nodes.size()) {
			//if(gr.colored(true)) {
			solutions++;
			Vector<Integer> solution = new Vector<Integer>(16);
			for(SimuNode n : nodes) {
				solution.add(n.color);
			}
			solutionVector.add(solution);
			//System.err.println(solution);
			return;
		}
		else { 
		for(int i=1;i<=chroma;i++) {
			if(available(node,i)) {
				nodes.get(node).color=i;
				solutionBuild(node+1);
			}
		}
		}
		nodes.get(node).color=0;
	}
	
	public void findHammingDistance() {
		totalDistance = 0;
		totalPermutations = 0;
		hammingSearch(0);
		System.err.println("totalDistance: "+totalDistance+" - totalPermutations: "+
				totalPermutations);
	}
	
	private long totalDistance = 0;
	private long totalPermutations = 0;
	public void hammingSearch(int node) {
		//System.err.println("Entering hammingSearch "+node);
		if(node==nodes.size()) {
			int distance = 0;
			int smallestDistance = 16;
			for(Vector<Integer> solution:solutionVector) {
				//make sure the solution is 16 large
				//assert(solution.size()==16):"Solution was " + solution.size();
				
				distance = 0;
				for(int i=0; i<16; i++) {
					if(nodes.get(i).color != solution.get(i)) distance ++;
				}
				//System.out.print(distance + ", ");
				//make sure the distance was less than 16
				//assert(distance < 16):"Distance was "+distance;
				if(distance < smallestDistance) smallestDistance = distance;
			}
			
			//System.out.println("\nsmallestDistance: "+smallestDistance+" - totalPermuations: "+
			//		totalPermutations);
			if(totalPermutations % 1000000 == 0) System.err.println(totalPermutations +" : "+ smallestDistance);
			totalDistance+=smallestDistance;
			totalPermutations++;

			return;
		}
		else { 
			//if(totalPermutations==1000000) return;
		for(int i=1;i<=chroma;i++) {
			nodes.get(node).color=i;
			hammingSearch(node+1);		
		}
		}
		nodes.get(node).color=0;
	}
	
	
	
	/*
	public void testColorability() {
		setColor(0);
	}
	
	public void setColor(int node) {
		//System.err.println("entering "+node);
		if(node==nodes.size()) {
			if(gr.colored(true)) {
				for(Node n:nodes)
					System.err.print(n.getIndex()+":"+n.color+" ");
				System.err.println();
			}
		}
		else for(int i=1;i<=chroma;i++) {
			nodes.get(node).color=i;
			setColor(node+1);
		}
		//System.err.println("leaving "+node);

	}
	*/
	
	/**
	 * Runs a simulation at the current existing state.
	 * 
	 * @param steps - the amount of steps allowed for a victory. This include Moves and Non-Moves.
	 * @return - true if the graph was solved, false otherwise.
	 */
	public boolean runSimulation(int steps) {
		Random rand=new Random();
		int next, minColorNum, colorChoice,nextColor;
		SimuNode n;
		int neighborColors[];
		Vector<Integer> minColors;
		NON_MOVES=0;
		MOVES=0;
		HALF_MOVES=0;
		NUM_CHOICES=0;
		LAST_MOVE=0;
		boolean isClean=false;
		
		
		if(DEBUG)System.err.println("Start Simulation ----------------------");
		
		for(int step=0;step<steps;step++) {
			
			/**
			 * random number [0 - numNodes) numNodes is usually 16
			 */
			next=rand.nextInt(numNodes);
			
			n=nodes.get(next);
			//color=n.color;
			neighborColors=new int[chroma+1];
			
			//set the amount of neighbors set at each color
			for(SimuNode ne:neighbors.get(next))
				neighborColors[ne.color]++;
			
			//find the color with the least neighbors set at
			minColorNum=numNodes;
			for(int j=1;j<=chroma;j++)
				if(neighborColors[j]<minColorNum) minColorNum=neighborColors[j];
			
			//put all the colors with equally small amounts in vector
			minColors=new Vector<Integer>();
			for(int j=1;j<=chroma;j++)
				if(neighborColors[j]==minColorNum) minColors.add(j);
			
			//if this node is already at the minimum color add to a non-move
			//and continue to the next iteration
			if(n.alg==Simulation.Algorithm.RANDOM_RAREST && 
					minColors.size()==1 && minColors.contains(n.color) || 
					n.alg==Simulation.Algorithm.RAREST && minColors.contains(n.color)) {
				if(!isClean) {
					if(!(isClean=isClean())) return false;
				}
				NON_MOVES++;
				if(DEBUG) {
					System.err.print("Step - "+step+". Node - "+n+" - Neighbor Colors:");
					for(int x:neighborColors) {
						System.err.print(x+" ");
					}
					
					System.err.print("\nNONMOVE!: ");
					for(SimuNode n2:nodes)
						System.err.print(n2+":"+n2.color+", ");
					System.err.println();
				}
				
				continue;
			}

			//find out the random number choice
			/**
			 * random number [0 - minColors.size()) always small 2 or 3 usually
			 */
			colorChoice=minColors.size()>1 ? rand.nextInt(minColors.size()) : 0;
			
			//change to the chosen color
			nextColor=minColors.get(colorChoice);
			NUM_CHOICES+=minColors.size();
			LAST_MOVE=step;
			if(n.color==nextColor) HALF_MOVES++;
			//else MOVES++;
			MOVES++;
			
			n.color=nextColor;
			isClean=false;
			
			
			if(DEBUG) {
				System.err.print("Step - "+step+". Node - "+n+" - Neighbor Colors:");
				for(int x:neighborColors) {
					System.err.print(x+" ");
				}
				
				System.err.print("\nMOVE!!!:  ");
				for(SimuNode n2:nodes)
					System.err.print(n2+":"+n2.color+", ");
				System.err.println();
			}
			
			if(gr.wellColored()) {
				if(SOLUTIONS){
					for(SimuNode currentNode:nodes) {
						System.out.print(currentNode+":"+currentNode.color+" "+
								(currentNode.index<10?" ":"")+
								(currentNode.color<10?" ":""));
						if(currentNode.index%10==9) System.out.println();
				}
				System.out.println();
				}
				return true;
			}
			
			//System.exit(0);
		}
		
		return false;
		/*
		if(gr.colored(true)) System.err.println("Graph solved in steps: "+(++i));
		else System.err.println("Graph NOT solved in steps: "+i+" : "+NUM_STEPS);
		
		return i;
		*/
	}
	
	
	public boolean isClean() {
		int minColorNum;
		int neighborColors[];
		Vector<Integer> minColors;
		SimuNode n;
		
	
		for(int next=0;next<nodes.size();next++) {
			n=nodes.get(next);
		
			//color=n.color;
			neighborColors=new int[chroma+1];
			
			//set the amount of neighbors set at each color
			for(SimuNode ne:neighbors.get(next))
				neighborColors[ne.color]++;
			
			//find the color with the least neighbors set at
			minColorNum=numNodes;
			for(int j=1;j<=chroma;j++)
				if(neighborColors[j]<minColorNum) minColorNum=neighborColors[j];
			
			//put all the colors with equally small amounts in vector
			minColors=new Vector<Integer>();
			for(int j=1;j<=chroma;j++)
				if(neighborColors[j]==minColorNum) minColors.add(j);
			
			//if this node is already at the minimum color add to a non-move
			//and continue to the next iteration
			if(n.alg==Simulation.Algorithm.RAREST) {
				if(!minColors.contains(n.color)) return true;
			}else if(n.alg==Simulation.Algorithm.RANDOM_RAREST)
				if(minColors.size()!=1 || !minColors.contains(n.color)) return true;
		}
		
		return false;
	}
	
	
	/**
	 * Sets the initial condition of the graph so that another simulation can be
	 * run without needing to recreate all the data structures.
	 */
	public void init() {
		
		gr.init();
		
		if(DEBUG) for(SimuNode n:nodes) {
			System.err.print(n+": neighbors are:");
			for(SimuNode ne:neighbors.get(n.index))
				System.err.print(" "+ne);
			System.err.println();
		}
	}
	
	/**
	 * Runs multiple simulations.
	 * 
	 * @param number - the number of simulations to run.
	 * @param STEPS - the number of steps to run each simulation.
	 */
	public String runSimulations(int num,int steps) {
		int sMoves=0,sNonMoves=0,sHalfMoves=0,sLastMove=0,sChoices=0,successes=0,
			fMoves=0,fNonMoves=0,fHalfMoves=0,fLastMove=0,fChoices=0,failures=0;
		boolean success;
		

		try {
		//BufferedWriter out=new BufferedWriter(new FileWriter("data"));
		
		for(int i=0;i<num;i++) {
			init();
			
			if(runSimulation(steps)) {
				if(DEBUG)System.err.println("Moves:"+MOVES+" NonMoves:"+NON_MOVES);
				sMoves+=MOVES;
				sNonMoves+=NON_MOVES;
				sHalfMoves+=HALF_MOVES;
				sLastMove+=LAST_MOVE;
				sChoices+=NUM_CHOICES;
				successes++;
				success=true;
			}
			else {
				fMoves+=MOVES;
				fNonMoves+=NON_MOVES;
				fHalfMoves+=HALF_MOVES;
				fLastMove+=LAST_MOVE;
				fChoices+=NUM_CHOICES;
				failures++;
				success=false;
			}
			DATA_OUT.write(CURRENT_FILE+SEP+i+SEP+(success?"1":"0")+SEP+MOVES+SEP+
					NON_MOVES+SEP+LAST_MOVE+SEP+HALF_MOVES+SEP+NUM_CHOICES/(double)MOVES+SEP2);
		}
		
		System.err.println((num==successes+failures)+":"+num+" - "+successes+failures);
				
		} catch (IOException e) {
			System.err.println("Error while opening the file: "+"data");
			e.printStackTrace();
		}
		
		//System.err.flush();
		System.err.println("------------------------------------------------------------");
		System.err.printf("Running %d simulations at %d steps.\n",num,steps);
		System.err.printf("Average Success Rate:%f.\nAverages Moves per Success:%f\n" +
				"Average Non-Moves per Success:%f\n",successes/(double)num,
				sMoves/(double)successes,sNonMoves/(double)successes);

		System.err.println("\n------------------------------------------------------------\n");
		//System.out.flush();
		//sMoves=0,sNonMoves=0,sHalfMoves=0,sLastMove=0,sChoices=0,successes=0,
		
		double successRate=successes/(double)num;
		double s=(double)successes;
		double sMoveAvg=sMoves/s,sNonMoveAvg=sNonMoves/s,sLastMoveAvg=sLastMove/s,
				sHalfMoveAvg=sHalfMoves/s,sChoicesAvg=sChoices/s/sMoves*s;
		double f=(double)failures;
		double fMoveAvg=fMoves/f,fNonMoveAvg=fNonMoves/f,fLastMoveAvg=fLastMove/f,
				fHalfMoveAvg=fHalfMoves/f,fChoicesAvg=fChoices/f/fMoves*f;
		
		
		
		return successRate+SEP+sMoveAvg+SEP+sNonMoveAvg+SEP+sLastMoveAvg+SEP+sHalfMoveAvg+SEP+
				sChoicesAvg+SEP+fMoveAvg+SEP+fNonMoveAvg+SEP+fLastMoveAvg+SEP+fHalfMoveAvg+SEP+
				fChoicesAvg;
		
		
		
		
		/*return "\tSuccess:"+successes/(double)num+
				"\tMoves:"+sMoves/(double)successes+
				"\tNonMoves:"+sNonMoves/(double)successes;*/
	
	}

	/**
	 * Creates a random graph for testing purposes.
	 * 
	 * @param size - the size of the graph
	 * @param fileName - the file to write the adjacency matrix to.
	 */
	public void writeTest(int size, String fileName) {
	    BufferedWriter file;
	    Random rand=new Random();
	    try {
			file = new BufferedWriter(new FileWriter(new File("matrix/"+fileName+".matrix")));
			for(int i=0;i<size;i++) {
				for(int j=0;j<size;j++)
					file.write(i!=j && rand.nextBoolean()?"1 ":"0 ");
				file.newLine();
			}
				
			file.close();	
				
		}catch(IOException e) {
			System.err.println("Error while opening file.");
			e.printStackTrace();
		}
	}
	/**
	 * Prints the chromatic number and number of solutions at this chromatic
	 * number for every matrix file in the passed in folder.
	 * 
	 * @param folderName - the folder which contains the matrix files to check 
	 */
	public void listChromaAndSolutions(String folderName) {
		File folder=new File(folderName);
		
		for(File file:folder.listFiles()){
			if(file.isHidden()) continue;
			SimulationHamming s=new SimulationHamming(file);
			System.out.print(file.getName().substring(0,file.getName().indexOf("."))+
					"\t-\tChromatic Number:"+s.chromaticNumber(0)+
					"\tSolutions:");
			System.out.println(s.solutions());
		}
	}
	
	/**
	 * Prints to a file the results of running runSimulation on
	 * all the graphs within that folder with the given amount of Simulations
	 * and number of steps
	 * 
	 * @param folderName - the folder containing the .matrix file to run
	 * @param fileName - the name of the file to print to
	 * @param num - the number of simulations to run per graph
	 * @param steps - the number of steps to run each simulation
	 */
	public static void simulateFolder(String folderName,String fileName,String dataFileName,int num,int steps) {
		File folder=new File(folderName);
		File outFile=new File(fileName);
		String curr;
		
		try {
		BufferedWriter out=new BufferedWriter(new FileWriter(outFile));
		out.write("FILE"+SEP+"SUCCESS"+SEP+"S_MOVES"+SEP+"S_NON_MOVES"+SEP+"S_LAST_MOVE"+
				SEP+"S_HALF_MOVES"+SEP+"S_NUM_CHOICES"+SEP+"F_MOVES"+SEP+"F_NON_MOVES"+
				SEP+"F_LAST_MOVE"+SEP+"F_HALF_MOVES"+SEP+"F_NUM_CHOICES"+SEP2);
		
		DATA_OUT=new BufferedWriter(new FileWriter(dataFileName));
		DATA_OUT.write("FILE"+SEP+"ITER"+SEP+"SOLVED"+SEP+"MOVES"+SEP+"NON_MOVES"+SEP+
				"LAST_MOVE"+SEP+"HALF_MOVES"+SEP+"NUM_CHOICES"+SEP2);

		for(File file:folder.listFiles()){
			if(file.isHidden()) continue;
			SimulationHamming s=new SimulationHamming(file);
			System.err.println("Setting the chromatic number to:"+s.chromaticNumber(0));
			s.CURRENT_FILE=file.getName().substring(0,file.getName().indexOf("."));
			curr=s.runSimulations(num, steps);
			
			out.write(file.getName().substring(0,file.getName().indexOf("."))+SEP+curr+SEP2);
			//out.flush();
			//DATA_OUT.flush();
		}
		out.close();
		DATA_OUT.close();
		
		} catch (IOException e) {
			System.err.println("Error while opening the file: "+outFile);
			e.printStackTrace();
		}
	}
	
	public static void hammingFolder(String folderName,String fileName) {
		File folder=new File(folderName);
		File outFile=new File(fileName);
		
		try {
		BufferedWriter out=new BufferedWriter(new FileWriter(outFile));
		out.write("FILE"+SEP+"CHROMA"+SEP+"SOLN"+SEP+"PERMS"+SEP+"HAMM"+SEP2);
		for(File file:folder.listFiles()){
			if(file.isHidden()) continue;
			SimulationHamming s=new SimulationHamming(file);
			System.err.println("Setting the chromatic number to:"+s.chromaticNumber(0));
			
			s.init();
			s.buildSolutionVector();
			//if(s.solutions > 24) continue;
			s.findHammingDistance();
			
			out.write(file.getName().substring(0,file.getName().indexOf("."))+
					SEP+s.chroma+SEP+s.solutions+SEP+s.totalPermutations+SEP+s.totalDistance);
			
			
			//s.CURRENT_FILE=file.getName().substring(0,file.getName().indexOf("."));
			//curr=s.runSimulations(num, steps);
			
			//out.write(file.getName().substring(0,file.getName().indexOf("."))+SEP+curr+SEP2);
			out.flush();
		}
		out.close();
		
		} catch (IOException e) {
			System.err.println("Error while opening the file: "+outFile);
			e.printStackTrace();
		}
	}
	
	
	/**
	 * The main driver; invoke this from the command line to start the process. 
	 * Supply it with 2 arguments: the name of the matrix file and the number of
	 * colors to simulate a test with.
	 */
	public static void main(String[] args) {
		/*File f=new File("matrix/4star13.matrix");
		Simulation s=new Simulation(f);
		System.err.println("Setting the chromatic number to:"+s.chromaticNumber(0));
		s.CURRENT_FILE=f.getName().substring(0,f.getName().indexOf("."));
		try {
			DATA_OUT=new BufferedWriter(new FileWriter("data"));
			DATA_OUT.write("FILE"+SEP+"ITER"+SEP+"SOLVED"+SEP+"MOVES"+SEP+"NON_MOVES"+SEP+
					"LAST_MOVE"+SEP+"HALF_MOVES"+SEP+"NUM_CHOICES"+SEP2);

			s.runSimulations(10, 100000);
			DATA_OUT.close();		
		} catch (IOException e) {
			e.printStackTrace();
		}*/

		//simulateFolder("matrix","RandomRarestSimulations","RandomRarestTrials",
		//		NUMBER_OF_SIMULATIONS,NUMBER_OF_STEPS);

		/*File f=new File("matrix/4star13.matrix");
		Simulation s = new Simulation(f);
		s.listChromaAndSolutions("matrix");
		/*s.chromaticNumber(0);
		s.init();
		s.buildSolutionVector();
		s.findHammingDistance();*/
		
		hammingFolder("hammingMatrix","hammingTest");
	}
	
	/**
	 * chrmatic number checking code
	 */
	/*
	ThreadMXBean bean = ManagementFactory.getThreadMXBean( );
	        
	double totalTime;
	long time=0;
	long start=bean.getCurrentThreadCpuTime();
	int chrNum;
	int totalChroma;
	
	int ITERS=100;
	
	BufferedWriter out=new BufferedWriter(new FileWriter(new File("info")));
	
	for(int i=44;i<=100;i++) {
		totalTime=0;
		totalChroma=0;
		for(int j=0;j<ITERS;j++) {
			s.writeTest(i,"test");
			f=new File("matrix/test.matrix");
			s=new Simulation(f,color,10);	
		
			start=bean.getCurrentThreadCpuTime();
			chrNum=s.chromaticNumber(1);
			time=bean.getCurrentThreadCpuTime()-start;
			totalTime+=time/(float)1000000000;
			totalChroma+=chrNum;
			
			out.write("NumNodes: "+s.numNodes+" ChrNum:"+chrNum+" @ "+time/(float)1000000000+"\n");
			out.flush();
		}
		System.out.println("NumNodes: "+i+" AverageChr: "+totalChroma/(float)ITERS+" AverageTime: "+totalTime/(float)ITERS);
	}
	out.close();
	*/
	
	/**
	 *  Argument parsing code that I don't want anymore
	 */
	/*
	if (args.length==0) {
		System.err.println("argument must be the name of a .matrix file");
		System.exit(01);
	}
	String fname= args[0];
	File f= new File(fname);
	if (!f.exists()) {
		System.err.println("the matrix file did not exist");
		System.exit(02);
	}
	
	if (args.length<2) {
		System.err.println("must supply the number of colors");
		System.exit(01);
	}int color = Integer.parseInt(args[1]);
	*/
}
